package com.hiwhitley.algorithm;

import java.util.Scanner;

/**
 * Created by hiwhitley on 2016/9/26.
 */
public class QueenPlace {

    static boolean place(int k, int j, int[] q) {
        int i = 1;
        while (i < k) {
            if (q[i] == j || Math.abs(q[i] - j) == Math.abs(k - i)) {
                return false;
            }
            i++;
        }

        return true;

    }

    public static void queen(int k, int n, int[] q) {
        int j;
        if (k > n) {
            printSolution(n, q);
        } else {
            for (j = 1; j <= n; j++) {
                if (place(k, j, q)) {
                    q[k] = j;
                    queen(k + 1, n, q);
                }
            }
        }
    }

    public static void printSolution(int n, int[] q) {
        for (int i = 1; i <= n; i++) {
            System.out.printf("(%d, %d) ", i, q[i]);
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        int[] q = new int[20];
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        queen(1, n, q);
    }
}
